#include <iostream>
#include <string>
using namespace std;
template<class KEY, class VALUE> class ECE462MAP
{
public:
  ECE462MAP();
  bool contains(KEY k);
  void insert(KEY k, VALUE v);
  VALUE get(KEY k);
  void remove(KEY k);
  int getSize() { return item; }
  virtual ~ECE462MAP();
private:
  KEY * kArray;
  VALUE * vArray;
  int size;
  int item;
};
template<class KEY, class VALUE> 
ECE462MAP<KEY, VALUE>::ECE462MAP()
{
  size = 10;
  item = 0;
  kArray = new KEY[size];
  vArray = new VALUE[size];
}

template<class KEY, class VALUE> 
ECE462MAP<KEY, VALUE>::~ECE462MAP()
{
  delete [] kArray;
  delete [] vArray;
}

template<class KEY, class VALUE> 
bool ECE462MAP<KEY, VALUE>::contains(KEY k)
{
  for (int i = 0; i < item; i ++)
    {
      if (kArray[i] == k)
        {
          return true;
        }
    }
  return false;
}

template<class KEY, class VALUE> 
void ECE462MAP<KEY, VALUE>::insert(KEY k, VALUE v)
{
  // check whether the key has already been seen
  for (int i = 0; i < item; i ++)
    {
      if (kArray[i] == k)
        {
          // replace the value
          vArray[i] = v;
          return;
        }
    }
  // new key
  if (item == size)
    {
      // need more space
      size *= 2;
      KEY * kArray2 = new KEY[size];
      VALUE * vArray2 = new VALUE[size];
      // copy elements
      for (int i = 0; i < item; i ++)
        {
          kArray2[i] = kArray[i];
          vArray2[i] = vArray[i];
        }
      delete [] kArray;
      delete [] vArray;
      kArray = kArray2;
      vArray = vArray2;
    }
  kArray[item] = k;
  vArray[item] = v;
  item ++;
}

template<class KEY, class VALUE> 
VALUE ECE462MAP<KEY, VALUE>::get(KEY k)
{
  // assume the set contains this key
  for (int i = 0; i < item; i ++)
    {
      if (kArray[i] == k)
        {
          return vArray[i];
        }
    }
  // should not reach here
  return vArray[0];
}
template<class KEY, class VALUE> 
void ECE462MAP<KEY, VALUE>::remove(KEY k)
{
  // assume the set contains this key
  for (int i = 0; i < item; i ++)
    {
      if (kArray[i] == k)
        {
          kArray[i] = kArray[item - 1];
          vArray[i] = vArray[item - 1];
          item --;
          return;
        }
    }
  // don't worry about shrinking the arrays
  // should not reach here
}
int main(int argc, char * argv[])
{
  ECE462MAP<string,int> mapsi;
  mapsi.insert("ece", 4);
  mapsi.insert("purdue", 6);
  mapsi.insert("lafayette", 2);
  cout << mapsi.get("lafayette") << endl; // 2
  mapsi.insert("lafayette", 9);
  cout << mapsi.get("lafayette") << endl; // 9
  cout << mapsi.getSize() << endl;        // 3
  mapsi.remove("purdue");
  cout << mapsi.getSize() << endl;        // 2
  cout << mapsi.contains("ece") << endl;  // 1
  ECE462MAP<int, string> mapis;
  mapis.insert(2, "WEST");
  cout << mapis.getSize() << endl;        // 1
  return 0;
}
